package 笔试真题;

import java.util.ArrayList;


public class Mihayou1 {
    public ArrayList<ArrayList<String>> ans = new ArrayList<>();

    public static void main(String[] args) {
        Mihayou1 mihayou1 = new Mihayou1();
        System.out.println(mihayou1.restoreIpAddresses("25525522135"));
    }

    public ArrayList<String> restoreIpAddresses(String ipStr) {
        // write code here
        traceBack(ipStr, 0, new ArrayList<>());
        ArrayList<String> res = new ArrayList<>();
        for (ArrayList<String> an : ans) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < an.size(); i++) {
                stringBuilder.append(an.get(i));
                if (i < an.size() - 1) {
                    stringBuilder.append(".");
                }
            }
            res.add(stringBuilder.toString());
        }
        return res;
    }

    private void traceBack(String ipStr, int i, ArrayList<String> list) {
        if (list.size() == 4) {
            if (i == ipStr.length() ) {
                ans.add(new ArrayList<>(list));
            } else {
                return;
            }
        }
        for (int j = 1; j <= 3; j++) {
            if (i + j <= ipStr.length()) {
                String substring = ipStr.substring(i, i+j);
                if (!checkLast(substring)) continue;
                list.add(substring);
                traceBack(ipStr, i + j, list);
                list.remove(list.size() - 1);
            }

        }
    }

    private boolean checkLast(String last) {
        int p = Integer.parseInt(last);
        return p >= 0 && p <= 255;
    }
}
